The present invention relates generally to an iterative graph algorithm accelerating method, and more particularly, but not by way of limitation, to a system, method, and computer program product for tuning a memory layout of a graph data structure such that an iterative graph algorithm can benefit from better cache locality.
Graph data structures are conventionally linear arrays and graph sizes are becoming bigger and more complex. Also, the structures are not algorithm-specific, which leaves much room for improvement in the graph data structures. Conventional graph analytics techniques suffer from irregular memory access patterns because neighboring nodes are not necessarily together, increasing cache sizes, Translation Look-Aside Buffer (TLB) misses and hamper a pre-fetcher, etc.
Thus, there is a need in the art for a technique that may re-order memory layouts such that memory access patterns are more regular, reduce cache misses, and facilitate a pre-fetcher.